1866D - Digital Wallet - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=100005,M=998244353;
const ll inf=100000000000000000ll;
const ld PI=3.141592653589793238;
int n,a[11][N],m,k;
long long dp[11][N][12];
long long dfs(int i,int j,int l){
    if(i>n)
        return dfs(1,j+1,max(l,j-k+2));
    if(j>m)
        return 0;
    if(dp[i][j][j-l+1]!=-1)
        return dp[i][j][j-l+1];
    if(l<=j&&l<=m-k+1)
        return dp[i][j][j-l+1]=max({dp[i][j][j-l+1],dfs(i+1,j,l+1)+a[i][j],dfs(i+1,j,l)});
    else
        return dp[i][j][j-l+1]=dfs(i+1,j,l);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    scanf("%d %d %d",&n,&m,&k);
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    cout<<dfs(1,1,1);
}